The present invention relates generally to the field of computing, and more particularly to combinatorial optimization.
In many real-world scenarios, finding optimal solutions to complex problems through exhaustive searching is not feasible. One real-world scenario, for example, may be determining the optimal way to deliver packages by truck. Optimal package delivery has been framed generically as the vehicle routing problem. The vehicle routing problem describes a scenario where a fleet of trucks leave a depot and must reach every delivery destination exactly one time and return to the depot at the conclusion of each truck's route. Additional constraints may be introduced to the vehicle routing problem such as accounting for the carrying capacity of the delivery vehicles generating a scenario known as the capacitated vehicle routing problem. Determining optimal routes to solve complex problems such as the capacitated vehicle routing problem may not be resolved using standard analytical techniques within practical computational or temporal limits.